﻿// 0918train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
公司用一个字符串来表示员工的出勤信息:
absent：缺勤
late：迟到
leaveearly：早退
present：正常上班
现需根据员工出勤信息，判断本次是否能获得出勤奖，能获得出勤奖的条件如下：
- 缺勤不超过一次
- 没有连续的迟到/早退
- 任意连续7次考勤，缺勤/迟到/早退不超过3次

输入描述
用户的考勤数据字符串，记录条数>=1;输入字符串长度<10000;不存在非法输入
2
present
present absent present present leaveearly present absent

输出描述
根据考勤数据字符串，如果能得到考勤奖，输出"true"，否则输出"false"
对于输入示例的结果应为true false

输入
2
present
present absent present present leaveearly present absent
输出
true false

1
present absent present present leaveearly present leaveearly present leaveearly present present leaveearly present leaveearly
 */
class Solution01
{
public:
    bool checkLong(vector<string>& check_v)
    {
        int check_v_size = check_v.size();
        if (check_v_size <= 7) return false;

        unordered_map<string, int>statistic = {
            {"absent", 0},{"late",0},{"leaveearly",0},{"present",0}
        };
        
        for (int i=0; i<7; i++)
        {
            string item = check_v[i];
            statistic[item] += 1;
        }

        unordered_set<string>error_set = {"absent","late","leaveearly"};
        int error_count = 0;
        for (auto&item: error_set)
        {
	        if (statistic.at(item)>0)
	        {
                error_count += statistic.at(item);
	        }
        }
        if (error_count > 3) return false;

        int window_length = 7;
        int old_left = 0;
        for (int left=1, right= window_length;right<check_v_size; left++,right++)
        {
            string old_item = check_v[old_left];
            if (error_set.count(old_item)>0)
            {
                error_count -= 1;
            }
            string new_item = check_v[right];
            if (error_set.count(new_item)>0)
            {
                error_count += 1;
            }
            if (error_count > 3)
            {
                return false;
            }
            old_left = left;
        }

        return true;
	    //checkLong
    }

    bool checkVerify(vector<string>&check_v)
    {
/*
absent：缺勤
late：迟到
leaveearly：早退
present：正常上班
*/
//缺勤不超过一次
//没有连续的迟到/早退
//任意连续7次考勤，缺勤/迟到/早退不超过3次
        unordered_map<string, int>statistic = {
        	{"absent", 0},{"late",0},{"leaveearly",0},{"present",0}
        };

        for (auto&item:check_v)
        {
            statistic[item] += 1;
            //for------
        }
        //缺勤不超过一次
        if (statistic["absent"] > 1) return false;

        int error = statistic["absent"] + statistic["late"] + statistic["leaveearly"];
        int check_v_size = check_v.size();
        if (check_v_size <= 7 && error > 3) return false;

        unordered_set<string>late_set = {"late","leaveearly"};
        for (int i=0; i< check_v_size-1; i++)
        {
            //没有连续的迟到/早退 late leaveearly
            string curr = check_v[i];
            string next = check_v[i + 1];
            if (late_set.count(curr) > 0 && late_set.count(next) > 0)
                return false;
            //for------
        }
        //小于7到此结束
        if (check_v_size <= 7)return true;

        //大于7用定长窗口扫一遍
        return checkLong(check_v);

	    //checkVerify
    }

    Solution01(vector<vector<string>>&origin_vec)
    {
        for (auto&item_v:origin_vec)
        {
            bool is_verify = checkVerify(item_v);
            if (is_verify)
            {
                result.push_back("true");
            }
            else
            {
                result.push_back("false");
            }

        }

        for (auto&res:result)
        {
            cout << res << ' ';
        }

	    //Solution01
    }
private:
    vector<string>result;
};


/*
题目描述
我们希望能够找到其中集中的矩形区域建设电站，能够获得良好的收益。

输入描述
第一行输入为调研的地区长，宽，以及准备建设的电站【长宽相等，为正方形】的边长最低要求的发电量
之后每行为调研区域每平方公里的发电量

输出描述
输出为这样的区域有多少人

示例1：
输入
2 5 2 6
1 3 4 5 8
2 3 6 7 1
输出
4
输入说明
调研的区域大小为长2宽5的矩形，我们要建设的电站的边长为2，建设电站最低发电量为6
输出说明
长宽为2的正方形满足发电量大于等于6的区域有4个

示例2：
输入
2 5 1 6
1 3 4 5 8
2 3 6 7 1
输出
3
 */
class Solution02
{
public:
    Solution02(vector<vector<int>>&grid,int width, int limit)
    {
        if (grid.empty()) return;
        row_size = grid.size(), col_size = grid[0].size();

        vector<vector<int>>pre_sum(row_size + 1, vector<int>(col_size + 1));

        //pre_sum[0][0]=0 pre_sum[0][c]=0 pre_sum[r][0]=0
        for (int r=1; r<=row_size; r++)
        {
	        for (int c=1; c<=col_size; c++)
	        {
                int new_num = grid[r - 1][c - 1];
                int repeat_area = pre_sum[r - 1][c - 1];
                pre_sum[r][c] = pre_sum[r][c - 1] + pre_sum[r - 1][c] - repeat_area + new_num;

	        }
        }

        int result = 0;
        //上边界r 下边界r+w-1 左边界c 右边界c+w-1
        //计算前缀和要把r+w-1, c+w-1包进去，所以pre_sum[r+w][c+w]
        for (int r=0; r+width<=row_size; r++)
        {
            for (int c=0; c+width<=col_size; c++)
            {
                int top = r, bottom = r + width - 1;
                int left = c, right = c + width - 1;

                int bigger = pre_sum[bottom + 1][right + 1];
                int top_area = pre_sum[top][right + 1];
                int left_area = pre_sum[bottom + 1][left];
                int repeat = pre_sum[top][left];

                int curr_area = bigger + repeat - top_area - left_area;
                if (curr_area >= limit) result += 1;
            }
        }

        cout << result;

	    //Solution02
    }
private:
    int row_size = 0, col_size = 0;
};


/*
 给定一个正整数数组，设为 nums，最大为100个成员
 求从第一个成员开始，正好走到数组最后一个成员，所使用的最少步骤数

要求：
1. 第一步必须从第一元素开始，且1<=第一步的步长<len/2;（len为数组的长度，需要自行解析）
2. 从第二步开始，只能以所在成员的数字走相应的步数，不能多也不能少，
如果目标不可达返回-1，只输出最少的步骤数量
3. 只能向数组的尾部走，不能往回走。

输入描述
由正整数组成的数组，以空格分隔，数组长度小于100，请自行解析数据数量。

输出描述
正整数，表示最少的步数，如果不存在输出-1

输入
7 5 9 4 2 6 8 3 5 4 3 9
输出
2

第一步： 第一个可选步长选择2，从第一个成员7开始走2步，到达9
第二步： 从9开始，经过自身数字9对应的9个成员到最后
 */
class Solution03
{
public:
    int isGetFinal(vector<int>& num_vec, int index)
    {
        int v_size = num_vec.size();
        int curr_step = 1;
        while (index<v_size)
        {
            int step = num_vec[index];
            index += step;
            curr_step += 1;
            if (index == v_size - 1)
            {
                return curr_step;
            }
        }

        return -1;
        //
    }

    Solution03(vector<int>&num_vec)
    {
        //第一元素开始，且1<=第一步的步长<len/2
        //只能以所在成员的数字走相应的步数
        int v_size = num_vec.size();

        int sub_size = 0;
        if (v_size%2==0)
        {
            sub_size = v_size / 2;
        }
        else
        {
            sub_size = v_size / 2 + 1;
        }

        int result = INT_MAX;
        for (int i = 1; i < sub_size; i++)
        {
            int need_step = isGetFinal(num_vec, i);
			if (need_step!=-1)
			{
                result = min(need_step, result);
			}
        }

        if (result==INT_MAX)
        {
            cout << -1;
            return;
        }
        cout << result;
	   //Solution03 
    }
};


/*
请实现一个简易内存池,根据请求命令完成内存分配和释放。
内存池支持两种操作命令，REQUEST和RELEASE，其格式为:
REQUEST=请求的内存大小 表示请求分配指定大小内存，如果分配成功，返回分配到的内存首地址；
如果内存不足，或指定的大小为0，则输出error
RELEASE=释放的内存首地址 表示释放掉之前分配的内存，释放成功无需输出，
如果释放不存在的首地址则输出error。

注意:
1. 内存池总大小为100字节
2. 内存池地址分配必须是连续内存，并优先从低地址分配
3. 内存释放后可被再次分配，已释放的内存在空闲时不能被二次释放
4. 不会释放已申请的内存块的中间地址
5. 释放操作只是针对首地址所对应的单个内存块进行操作，不会影响其它内存块

输入描述
首行为整数N，表示操作命令的个数，取值范围0<N<=100。
接下来的N行，每行将给出一个操作命令，操作命令和参数之间用"="分割。

输出描述
REQUEST
分配成功，返回分配到的内存首地址
如果内存不足，或指定的大小为0，则输出error

RELEASE
释放的内存首地址 表示释放掉之前分配的内存，释放成功无需输出
释放不存在的首地址则输出error

输入
2
REQUEST=10
REQUEST=20
输出
0
10

输入
5
REQUEST=10
REQUEST=20
RELEASE=20
RELEASE=10
REQUEST=10
输出
0
10
error
10
 */
class Solution04
{
public:

};


int main()
{
	{
        int v_size;
        cin >> v_size;

        vector<string>order_v(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> order_v[i];
        }

        Solution04 solu(order_v);

        return 0;
	}
	{
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;

        vector<int>num_vec;
        while (oh_sstream>>token)
        {
            num_vec.push_back(stoi(token));
        }

        Solution03 solu(num_vec);

        return 0;
	}
	{
        int row_size, col_size;
        cin >> row_size >> col_size;
        int width, limit;
        cin >> width >> limit;

        vector<vector<int>>grid(row_size, vector<int>(col_size));

        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
                cin >> grid[r][c];
	        }
        }

        Solution02 solu(grid, width, limit);

        return 0;
	}
    int v_size;
    cin >> v_size;
    cin.ignore();

    vector<vector<string>>origin_vec;
    for (int i=0; i<v_size;i++)
    {
        vector<string>item_v;
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (oh_sstream>>token)
        {
            item_v.push_back(token);
        }
        origin_vec.push_back(item_v);
    }

    Solution01 solu(origin_vec);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
